home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1995 July / macformat-026.iso / mac / Shareware City / Developers / berkeleydb1.73 / Berkeley_db / btree / bt_delete.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-27  |  9.2 KB  |  330 lines  |  [TEXT/MPS ]
  1. /*-
  2.  * Copyright (c) 1990, 1993
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)bt_delete.c    8.2 (Berkeley) 9/7/93";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #if defined(macintosh) && (defined(powerc) || defined(__powerc))
  42. #include "OurMalloc.h"
  43. #endif
  44.  
  45. #include <sys/types.h>
  46.  
  47. #include <errno.h>
  48. #include <stdio.h>
  49. #include <string.h>
  50.  
  51. #include <db.h>
  52. #include "btree.h"
  53.  
  54. static int bt_bdelete __P((BTREE *, const DBT *));
  55.  
  56. /*
  57.  * __BT_DELETE -- Delete the item(s) referenced by a key.
  58.  *
  59.  * Parameters:
  60.  *    dbp:    pointer to access method
  61.  *    key:    key to delete
  62.  *    flags:    R_CURSOR if deleting what the cursor references
  63.  *
  64.  * Returns:
  65.  *    RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
  66.  */
  67. int
  68. __bt_delete(dbp, key, flags)
  69.     const DB *dbp;
  70.     const DBT *key;
  71.     u_int flags;
  72. {
  73.     BTREE *t;
  74.     int status;
  75.  
  76.     t = dbp->internal;
  77.  
  78.     /* Toss any page pinned across calls. */
  79.     if (t->bt_pinned != NULL) {
  80.         mpool_put(t->bt_mp, t->bt_pinned, 0);
  81.         t->bt_pinned = NULL;
  82.     }
  83.  
  84.     if (ISSET(t, B_RDONLY)) {
  85.         errno = EPERM;
  86.         return (RET_ERROR);
  87.     }
  88.  
  89.     switch(flags) {
  90.     case 0:
  91.         status = bt_bdelete(t, key);
  92.         break;
  93.     case R_CURSOR:
  94.         /*
  95.          * If flags is R_CURSOR, delete the cursor; must already have
  96.          * started a scan and not have already deleted the record.  For
  97.          * the delete cursor bit to have been set requires that the
  98.          * scan be initialized, so no reason to check.
  99.          */
  100.         if (!ISSET(t, B_SEQINIT))
  101.                         goto einval;
  102.         status = ISSET(t, B_DELCRSR) ?
  103.             RET_SPECIAL : __bt_crsrdel(t, &t->bt_bcursor);
  104.         break;
  105.     default:
  106. einval:        errno = EINVAL;
  107.         return (RET_ERROR);
  108.     }
  109.     if (status == RET_SUCCESS)
  110.         SET(t, B_MODIFIED);
  111.     return (status);
  112. }
  113.  
  114. /*
  115.  * BT_BDELETE -- Delete all key/data pairs matching the specified key.
  116.  *
  117.  * Parameters:
  118.  *    tree:    tree
  119.  *    key:    key to delete
  120.  *
  121.  * Returns:
  122.  *    RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
  123.  */
  124. static int
  125. bt_bdelete(t, key)
  126.     BTREE *t;
  127.     const DBT *key;
  128. {
  129.     EPG *e, save;
  130.     PAGE *h;
  131.     pgno_t cpgno, pg;
  132.     indx_t cindex;
  133.     int deleted, dirty1, dirty2, exact;
  134.  
  135.     /* Find any matching record; __bt_search pins the page. */
  136.     if ((e = __bt_search(t, key, &exact)) == NULL)
  137.         return (RET_ERROR);
  138.     if (!exact) {
  139.         mpool_put(t->bt_mp, e->page, 0);
  140.         return (RET_SPECIAL);
  141.     }
  142.  
  143.     /*
  144.      * Delete forward, then delete backward, from the found key.  The
  145.      * ordering is so that the deletions don't mess up the page refs.
  146.      * The first loop deletes the key from the original page, the second
  147.      * unpins the original page.  In the first loop, dirty1 is set if
  148.      * the original page is modified, and dirty2 is set if any subsequent
  149.      * pages are modified.  In the second loop, dirty1 starts off set if
  150.      * the original page has been modified, and is set if any subsequent
  151.      * pages are modified.
  152.      *
  153.      * If find the key referenced by the cursor, don't delete it, just
  154.      * flag it for future deletion.  The cursor page number is P_INVALID
  155.      * unless the sequential scan is initialized, so no reason to check.
  156.      * A special case is when the already deleted cursor record was the
  157.      * only record found.  If so, then the delete opertion fails as no
  158.      * records were deleted.
  159.      *
  160.      * Cycle in place in the current page until the current record doesn't
  161.      * match the key or the page is empty.  If the latter, walk forward,
  162.      * skipping empty pages and repeating until a record doesn't match
  163.      * the key or the end of the tree is reached.
  164.      */
  165.     cpgno = t->bt_bcursor.pgno;
  166.     cindex = t->bt_bcursor.index;
  167.     save = *e;
  168.     dirty1 = 0;
  169.     for (h = e->page, deleted = 0;;) {
  170.         dirty2 = 0;
  171.         do {
  172.             if (h->pgno == cpgno && e->index == cindex) {
  173.                 if (!ISSET(t, B_DELCRSR)) {
  174.                     SET(t, B_DELCRSR);
  175.                     deleted = 1;
  176.                 }
  177.                 ++e->index;
  178.             } else {
  179.                 if (__bt_dleaf(t, h, e->index)) {
  180.                     if (h->pgno != save.page->pgno)
  181.                         mpool_put(t->bt_mp, h, dirty2);
  182.                     mpool_put(t->bt_mp, save.page, dirty1);
  183.                     return (RET_ERROR);
  184.                 }
  185.                 if (h->pgno == save.page->pgno)
  186.                     dirty1 = MPOOL_DIRTY;
  187.                 else
  188.                     dirty2 = MPOOL_DIRTY;
  189.                 deleted = 1;
  190.             }
  191.         } while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0);
  192.  
  193.         /*
  194.          * Quit if didn't find a match, no next page, or first key on
  195.          * the next page doesn't match.  Don't unpin the original page
  196.          * unless an error occurs.
  197.          */
  198.         if (e->index < NEXTINDEX(h))
  199.             break;
  200.         for (;;) {
  201.             if ((pg = h->nextpg) == P_INVALID)
  202.                 goto done1;
  203.             if (h->pgno != save.page->pgno)
  204.                 mpool_put(t->bt_mp, h, dirty2);
  205.             if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) {
  206.                 mpool_put(t->bt_mp, save.page, dirty1);
  207.                 return (RET_ERROR);
  208.             }
  209.             if (NEXTINDEX(h) != 0) {
  210.                 e->page = h;
  211.                 e->index = 0;
  212.                 break;
  213.             }
  214.         }
  215.  
  216.         if (__bt_cmp(t, key, e) != 0)
  217.             break;
  218.     }
  219.  
  220.     /*
  221.      * Reach here with the original page and the last page referenced
  222.      * pinned (they may be the same).  Release it if not the original.
  223.      */
  224. done1:    if (h->pgno != save.page->pgno)
  225.         mpool_put(t->bt_mp, h, dirty2);
  226.  
  227.     /*
  228.      * Walk backwards from the record previous to the record returned by
  229.      * __bt_search, skipping empty pages, until a record doesn't match
  230.      * the key or reach the beginning of the tree.
  231.      */
  232.     *e = save;
  233.     for (;;) {
  234.         if (e->index)
  235.             --e->index;
  236.         for (h = e->page; e->index; --e->index) {
  237.             if (__bt_cmp(t, key, e) != 0)
  238.                 goto done2;
  239.             if (h->pgno == cpgno && e->index == cindex) {
  240.                 if (!ISSET(t, B_DELCRSR)) {
  241.                     SET(t, B_DELCRSR);
  242.                     deleted = 1;
  243.                 }
  244.             } else {
  245.                 if (__bt_dleaf(t, h, e->index) == RET_ERROR) {
  246.                     mpool_put(t->bt_mp, h, dirty1);
  247.                     return (RET_ERROR);
  248.                 }
  249.                 if (h->pgno == save.page->pgno)
  250.                     dirty1 = MPOOL_DIRTY;
  251.                 deleted = 1;
  252.             }
  253.         }
  254.  
  255.         if ((pg = h->prevpg) == P_INVALID)
  256.             goto done2;
  257.         mpool_put(t->bt_mp, h, dirty1);
  258.         dirty1 = 0;
  259.         if ((e->page = mpool_get(t->bt_mp, pg, 0)) == NULL)
  260.             return (RET_ERROR);
  261.         e->index = NEXTINDEX(e->page);
  262.     }
  263.  
  264.     /*
  265.      * Reach here with the last page that was looked at pinned.  Release
  266.      * it.
  267.      */
  268. done2:    mpool_put(t->bt_mp, h, dirty1);
  269.     return (deleted ? RET_SUCCESS : RET_SPECIAL);
  270. }
  271.  
  272. /*
  273.  * __BT_DLEAF -- Delete a single record from a leaf page.
  274.  *
  275.  * Parameters:
  276.  *    t:    tree
  277.  *    index:    index on current page to delete
  278.  *
  279.  * Returns:
  280.  *    RET_SUCCESS, RET_ERROR.
  281.  */
  282. int
  283. __bt_dleaf(t, h, index)
  284.     BTREE *t;
  285.     PAGE *h;
  286.     int index;
  287. {
  288.     register BLEAF *bl;
  289.     register indx_t *ip, offset;
  290.     register size_t nbytes;
  291.     register int cnt;
  292.     char *from;
  293.     void *to;
  294.  
  295.     /*
  296.      * Delete a record from a btree leaf page.  Internal records are never
  297.      * deleted from internal pages, regardless of the records that caused
  298.      * them to be added being deleted.  Pages made empty by deletion are
  299.      * not reclaimed.  They are, however, made available for reuse.
  300.      *
  301.      * Pack the remaining entries at the end of the page, shift the indices
  302.      * down, overwriting the deleted record and its index.  If the record
  303.      * uses overflow pages, make them available for reuse.
  304.      */
  305.     to = bl = GETBLEAF(h, index);
  306.     if (bl->flags & P_BIGKEY && __ovfl_delete(t, bl->bytes) == RET_ERROR)
  307.         return (RET_ERROR);
  308.     if (bl->flags & P_BIGDATA &&
  309.         __ovfl_delete(t, bl->bytes + bl->ksize) == RET_ERROR)
  310.         return (RET_ERROR);
  311.     nbytes = NBLEAF(bl);
  312.  
  313.     /*
  314.      * Compress the key/data pairs.  Compress and adjust the [BR]LEAF
  315.      * offsets.  Reset the headers.
  316.      */
  317.     from = (char *)h + h->upper;
  318.     memmove(from + nbytes, from, (char *)to - from);
  319.     h->upper += nbytes;
  320.  
  321.     offset = h->linp[index];
  322.     for (cnt = index, ip = &h->linp[0]; cnt--; ++ip)
  323.         if (ip[0] < offset)
  324.             ip[0] += nbytes;
  325.     for (cnt = NEXTINDEX(h) - index; --cnt; ++ip)
  326.         ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1];
  327.     h->lower -= sizeof(indx_t);
  328.     return (RET_SUCCESS);
  329. }
  330.